package leecode

func combinationSum3(k int, n int) (result [][]int) {
	var backtracking func(k, n, startIndex int)
	path := make([]int, 0, k)
	backtracking = func(k, n, startIndex int) {
		if len(path) == k {
			if n == 0 {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
			}
			return
		}
		for i := startIndex; i <= 9; i++ {
			n = n - i
			//处理节点
			path = append(path, i)
			backtracking(k, n, i+1)
			n = n + i //还原
			path = path[:len(path)-1]
		}
	}
	backtracking(k, n, 1)
	return
}
